import java.util.*;


public class CombinationSum {
	public void tester() {
		int [] a = {1,2,3,4,5,6};
		combinationSum(a, 7);
		
		for(int i = 0 ; i < result.size(); i++) {
			for(int j = 0 ; j < result.get(i).size(); j++) {
				 System.out.print(result.get(i).get(j)+" ");
			}
			System.out.println();
		}
	}
	
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	Arrays.sort(candidates);
        
        ArrayList <Integer> p = new ArrayList <Integer> ();
    	combina(target, candidates, p, 0);
        
        return result;
    }
    
    List<List<Integer>> result = new ArrayList <List <Integer>>();
    
    public void combina(int t, int [] c, ArrayList <Integer> p, int start) {
    	if(t == 0) {
    		result.add(p);
    		return;
    	}
    	
    	int prev = 0;
    	
    	int i = start;
    	
//    	if(p.size() > 0) i = bs(c, p.get(p.size()-1));
    	
    	for( ; i < c.length && c[i] <= t; i++) {
    		if(prev == c[i]) continue;
    		prev = c[i];
    		
			ArrayList <Integer> p2 = new ArrayList <Integer> ();
			p2.addAll(p);
			p2.add(c[i]);
			combina(t-c[i], c, p2, i+1);
		}
    }
    
    public void printAll(ArrayList <Integer> p) {
    	for(int j = 0 ; j < p.size(); j++) {
			System.out.print(p.get(j)+" ");
		}
    	System.out.println();
    }
}